Data routing on data packet networks (DPN) has continually evolved through introduction of new data routing protocols and strategies. Most routing protocols are based on shortest-path algorithms, which can be classified generally as distance-vector algorithms and link-state or topology-broadcast algorithms. In a distance-vector protocol a data router knows the length of the shortest path from each neighbor router in a network to every network destination. In a link-state protocol, each router broadcasts the state of every router's adjacent link to every other router in the network topology. The routers use the broadcast information to build a network topology, which is then used to compute shortest paths to other routers and hosts in the network. A goal of state-of-the-art routing over a data-packet-network is to maintain, as much as possible, loop-free data paths throughout the network.
Much detailed information of existing network protocols and methods for loop-free data routing is presented in a paper entitled Loop-Free Multipath Routing Using Generalized Diffusing Computations authored by William T. Zaumen and J. J. Garcia-Luna-Aceves. This paper is included herein as background information by reference. The referenced paper also has disclosure referenced in a U.S. Pat. No. 5,881,243 entitled “System for maintaining multiple loop free paths between source node and destination node in computer network” filed on May 7, 1997, the listed inventors being the same individuals that authored the referenced paper.
The provision of multiple paths in existing network routing protocols is somewhat limited. For example, open-shortest-path-first (OSPF) protocol enables a router to choose more than one network path to a same destination only in the event that multiple paths of a minimum cost exist and are defined. Interior-gateway-routing-protocol (IGRP) enables a router to forward data packets through network paths having lengths less than the product of shortest path multiplied by a variance factor provided by a network administrator.
More recently, diffusing algorithms have been introduced to enable more efficient loop-free routing by introducing the concept of a shortest multipath. A shortest multipath is quantified by a directed acyclic graph (DAG), which is defined by entries in routing tables (forwarding tables) of successor routers in all of the paths from a source to a destination that are guaranteed to be loop-free at any given point in time. A state-of-the-art protocol known as diffusing algorithm for shortest multipath (DASM) enables guaranteed loop-free routing.
DASM introduces a distributive approach in the synchronization of tables between routers. DASM maintains loop-freedom through the use of multiple successors for every destination at each router in the network. The only information exchanged between neighbor routers consists of vectors of shortest distances to destinations. Synchronization of tables between routers produces considerable overhead with DASM, however, the overhead can be reduced by introducing a feasibility condition to determine when any router may update its routing table without synchronizing with others. Considerable detailed notation is presented in the paper and patent referenced above, the notation explaining various aspects and conditions of DASM.
The referenced paper and U.S. Pat. No. 5,881,243 describes a system for maintaining routing tables at each router in a computer network. The system is based on (a) a feasibility condition that provides multiple loop-free paths through a computer network and that minimizes the amount of synchronization among routers necessary for the correct operation of a routing algorithm, and (b) a method that manages the set of successors during the time it synchronizes its routing-table update activity with other routers, in order to efficiently compute multiple loop-free paths, including the shortest path, through a computer network.
It is desired, in addition to loop free routing, that data traveling in a network from multiple sources to multiple destinations be managed in terms of network paths such that the network does not become un-evenly congested. The system described above utilizing DASM cannot provide efficient data flow load balancing such that one or more portions of the network are not overloaded or underutilized with respect to data carried over multiple connections having available bandwidth for data transmission, which may vary considerably due to various conditions monitorable and determinable in a given network.
Therefore, it is the goal of the present invention to provide a series of improvements to the general diffusing algorithm and concept of DASM that enable more administrative control over network-path utilization and more flexible consideration at routing points of shortest multipaths.